/* 870. 优势洗牌 */
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */

/* 
    贪心
    我们首先分别将nums1和nums2进行排序，随后只需要不断考虑两个数组的首个
    元素
    如果nums1的首个元素大于nums2的首个元素，那么就将他们在答案中对应起来
    同时从数组中移除这两个元素，并增加一点优势
    如果nums1的首个元素小于等于nums2的首个元素，那么移除num1的首个元素

    田忌赛马：打不过就送人投去拼对方最强的
*/
var advantageCount = function (nums1, nums2) {
	const n = nums1.length
	const idx1 = Array(n).fill(0)
	const idx2 = Array(n).fill(0)
	for (let i = 0; i < n; i++) {
		idx1[i] = i
		idx2[i] = i
	}

	idx1.sort((i, j) => nums1[i] - nums1[j])
	idx2.sort((i, j) => nums2[i] - nums2[j])

	const ans = Array(n).fill(0)
	let left = 0,
		right = n - 1
	for (let i = 0; i < n; ++i) {
		if (nums1[idx1[i]] > nums2[idx2[left]]) {
			ans[idx2[left]] = nums1[idx1[i]]
			++left
		} else {
			ans[idx2[right]] = nums1[idx1[i]]
			--right
		}
	}
	return ans
}
var advantageCount = function (nums1, nums2) {
	const len = nums1.length
	const ans = new Array(len).fill(0)
	nums1.sort((a, b) => a - b)
	/*
        nums2 中元素的顺序不能变，因为计算结果的顺序依赖nums2的顺序
        所以不能直接对nums2进行排序。而是利用其它数据结构来辅助
    */
	let indexB = Array(len)
		.fill(0)
		.map((v, i) => i)
	indexB.sort((i, j) => nums2[i] - nums2[j])
	/*
        比方说:nums2为[13,25,32,11] 排序的话 => [11,13,25,32]
        indexB 里面存放的就是 [3,0,1,2]
        3: 原来11所在的索引位置
        0：原来13所在的索引
        1：原来25所在的索引
    */
	let i = 0 // 田忌的马排位
	let j = 0 // 齐王的马排位
	/*
         B 从 len - 1 开始（如果A当前最小的数无法对B形成优势，
         就需要让它覆盖B当前最大的数字
         ）
    */
	let k = len - 1
	while (i < len) {
		/* 
            跟对应的排位的马比较，能比得过的话就拼，拼不过就舍弃它去对抗对手最强的
        */
		if (nums1[i] > nums2[indexB[j]]) {
			ans[indexB[j]] = nums1[i]
			j++
		} else {
			ans[indexB[k]] = nums1[i]
			k--
		}
		i++
	}

	return ans
}
const result = advantageCount([12, 24, 8, 32], [13, 25, 32, 11])
console.log('result :>>', result)
